/**
 * @param {string[]} words
 * @return {string[]}
 */


var wordBreak = function (sentence: string, words: string[]) {

    const set = new Set(words)


    const cacheSolutionFor: { [k: number]: string[] } = []
    cacheSolutionFor[sentence.length] = [""]

    function dfs(s: string, len: number): string[] {


        if (cacheSolutionFor[len]) {
            return cacheSolutionFor[len]
        } else {


            cacheSolutionFor[len] = []

            for (let l = len + 1; l <= s.length; l++) {

                const word = s.slice(len, l)

                if (set.has(word)) {

                    for (const sol of dfs(s, l)) {

                        cacheSolutionFor[len].push(
                            [word, sol].join(' ').trim()
                        )
                    }
                }
            }
        }

        return cacheSolutionFor[len]
    }


    dfs(s, 0)


    return cacheSolutionFor[0]
}


let s = "catsanddog"
let wordDict = ["cat", "cats", "and", "sand", "dog"]

s = "aaaaaaaaaaaaaaaaaaaaaaa"
wordDict = ["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"]


console.log(wordBreak(s, wordDict));
